ניתוח לשיעורין:

• מתמקד בניתוח סיבוכיות הזמן במקרה הגרוע של סדרה של פעולות על מבנה נתונים, ולא של פעולה בודדת.
• הרעיון המרכזי: גם אם פעולה אחת מסוימת בסדרה היא מאוד יקרה (למשל $\mathrm{\Theta }(n)$), ייתכן שעלות הפעולה הממוצעת לאורך כל הסדרה תהיה נמוכה משמעותית (למשל $\mathrm{\Theta }(1)$).
• אם $n$ פעולות לוקחות $T(n)$ זמן במקרה הגרוע, העלות לשיעורין של פעולה בודדת היא $T(n)/n$.
• אנלוגיה - נסיעה ברכב.
  • ברוב הימים העלות היא אפס (לא מתדלקים), וביום אחד העלות גבוהה (תדלוק מלא).
  • העלות לשיעורין היא חלוקת ההוצאה הכוללת במספר ימי הנסיעה כדי לקבל את ה"עלות הממוצעת" ליום.

שיטות לניתוח לשיעורין:

• שיטת הקיבוץ (Aggregate analysis method):
  • מחשבים ישירות את העלות הכוללת של $n$ פעולות, כלומר חוסמים את הסכום $T(n)=\sum _{i=1}^n{c}_i$ (כאשר $c_i$ היא העלות האמיתית של הפעולה ה-$i$). העלות לשיעורין היא הסכום הזה חלקי $n$.
• שיטת החיוב (Accounting method):
  • לכל פעולה נקבע "חיוב" (Charge / ${\hat{c}}_i$) שיכול להיות שונה מהעלות האמיתית שלה ($c_i$).
  • מחייבים פעולות זולות בסכום גבוה מעלותן האמיתית. ההפרש נשמר כ"קרדיט" (או "דולרים") בתוך מבנה הנתונים.
  • כאשר מגיעה פעולה יקרה, משתמשים ב"דולרים" שנצברו כדי לשלם עליה.
  • כלל ברזל: אסור להיכנס למינוס (חוב). בכל שלב נתון $j$, סך העלויות האמיתיות חייב להיות קטן או שווה לסך החיובים: $\sum _{i=1}^j{c}_i\le \sum _{i=1}^j{\hat{c}}_i$.

דוגמאות לניתוחי לשיעורין:

• מחסנית עם פעולת Multipop:
  • מחסנית התומכת ב-Push, Pop ו-Multipop(k) (המוציאה $k$ איברים או מרוקנת את המחסנית). העלות של Multipop יכולה להיות $O(n)$ במקרה הגרוע.
  • בשיטת הקיבוץ:
    • מספר הפעמים שניתן להוציא איבר (Pop/Multipop) חסום על ידי מספר האיברים שהוכנסו (Push), שהוא לכל היותר $n$.
    • לכן, העלות הכוללת ל-$n$ פעולות היא $\mathrm{\Theta }(n)$, והעלות לשיעורין לפעולה היא $\mathrm{\Theta }(1)$.
  • בשיטת החיוב:
    • נחייב Push ב-2 דולר (1 לעלות ההכנסה, 1 נשמר על האיבר).
    • נחייב Pop ו-Multipop ב-0 דולר.
    • כששולפים איבר, משתמשים בדולר השמור עליו כדי לשלם את העלות. לכן העלות לשיעורין היא $\mathrm{\Theta }(1)$.
• מונה בינארי (Binary Counter):
  • מונה המבצע פעולת Increment (הגדלה ב-1) על ידי הפיכת ביטים. עלות פעולה היא מספר הביטים שמשתנים. פעולה בודדת יכולה לעלות $O(k)$.
  • בשיטת הקיבוץ:
    • הביט הראשון מתהפך בכל פעולה, הביט השני ב-$1/2$ מהפעולות, הביט ה-$i$ ב-$1/2^i$ מהפעולות.
    • סכום ההיפוכים ל-$n$ פעולות מתכנס ל-$2n$. לכן העלות לשיעורין היא $\mathrm{\Theta }(1)$.
  • בשיטת החיוב:
    • נחייב הפיכת ביט מ-$0$ ל-$1$ ב-2 דולר (1 משלם על ההיפוך הנוכחי, 1 נשמר על הביט שהפך ל-1).
    • הפיכת ביט מ-$1$ ל-$0$ ממומנת על ידי הדולר שנשמר עליו (חיוב 0).
    • מאחר שבכל Increment הופכים בדיוק אפס אחד לאחד, החיוב תמיד יהיה 2 דולר, ולכן העלות לשיעורין $\mathrm{\Theta }(1)$.
• טבלאות גיבוב דינאמיות (Dynamic Hash Tables):
  • שמירה על "גורם עומס" (Load factor - $\alpha$) בתחום $1/4\le \alpha \le 1$ כדי להבטיח זמן חיפוש צפוי של $\mathrm{\Theta }(1)$ וצריכת זיכרון של $\mathrm{\Theta }(n)$.
  • הכנסות בלבד:
    • כאשר הטבלה מתמלאת ($\alpha =1$), מכפילים את גודלה ומעתיקים את האיברים (גיבוב מחדש).
    • חיוב הכנסה ב-3 דולרים (1 להכנסה, 2 נשמרים בטבלה) מבטיח שכשנגיע לטבלה מלאה יהיה לנו מספיק "דולרים" כדי לממן את עלות ההעתקה לטבלה החדשה.
  • הכנסות ומחיקות:
    • אם נקטין טבלה מיד כשהיא מגיעה לחצי ($\alpha =1/2$), סדרה גרועה של (הכנסה, מחיקה, הכנסה...) תגרור גיבוב מחדש בכל שלב וסיבוכיות $\mathrm{\Theta }(n)$ לפעולה.
    • הפתרון הוא להקטין את הטבלה רק כאשר $\alpha =1/4$, מה שמאפשר לצבור מספיק חיובים מהמחיקות כדי לממן את העתקת האיברים בעת הכיווץ.

תובנות מהתרגול:

• ניתוח לשיעורין הוא דטרמניסטי - אין שימוש בהסתברות בניתוח העלות לשיעורין, בוחרים את הסדרה הרעה ביותר מבחינת זמן ריצה ומחלקים בכמות הפעולות.
• מחסנית עם גיבויים:
  • מחסנית שבכל שלב ישנם לכל היותר K איברים במחסנית.
  • המחסנית ממומשת על ידי מערך (זמני ההכנסה וההוצאה קבועים).
  • לאחר כל K פעולות, מבוצע שכפול של כלל האיברים הנמצאים במכנסית לגיבוי.
  • העלות לשיעורין: של פעולת ההכנסה וההוצאה ברצף של n > k היא טטא של 1.